package com.lw.leetcode.other.c;

/**
 * Created with IntelliJ IDEA.
 * 2081. k 镜像数字的和
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/31 11:36
 */
public class KMirror {

    public static void main(String[] args) {
        KMirror test = new KMirror();

        // 25
//        int k = 2;
//        int n = 5;

        // 499
//        int k = 3;
//        int n = 7;

        // 20379000
        int k = 7;
        int n = 17;

        long l = test.kMirror(k, n);
        System.out.println(l);

        for (int i = 2; i <= 9; i++) {
            for (int j = 1; j <= 30; j++) {
                long t1 = System.currentTimeMillis();
                long v = test.kMirror(i, j);
//                if (v != v2) {
//                    System.out.println();
//                    System.out.println(v + "  " + (System.currentTimeMillis() - t));
//                }
            }
        }

    }

    public long kMirror(int k, int n) {
        long sum = 0;
        String[] ints = new String[32];
        ints[1] = "1";
        for (int i = 2; i < 32; i++) {
            ints[i] = ints[i - 1] + "0";
        }
        int flag = 2;
        char[] arr = {'1'};
        while (n > 0) {
            int length = arr.length;
            int other = (flag & 1) == 0 ? length - 2 : length - 1;
            char[] newArr = new char[length + 1 + other];
            System.arraycopy(arr, 0, newArr, 0, length);
            int index = length;
            for (int i = other; i >= 0; i--) {
                newArr[index++] = arr[i];
            }
            long value = getValue(newArr, k);
            if (check(value)) {
                sum += value;
                n--;
            }
            arr = getNext(arr, k);
            if (arr == null) {
                flag++;
                arr = ints[flag >> 1].toCharArray();
            }
        }
        return sum;
    }

    private boolean check (long value) {
        char[] arr = String.valueOf(value).toCharArray();
        int length = arr.length;
        for (int i = length >> 1; i >= 0; i--) {
            if (arr[i] != arr[length - i - 1]) {
                return false;
            }
        }
        return true;
    }

    private char[] getNext(char[] arr, int k) {
        boolean f = true;
        for (char c : arr) {
            if ((c - '0') != k - 1) {
                f = false;
                break;
            }
        }
        if (f) {
            return null;
        }
        int length = arr.length;
        int v = 1;
        int max = k + '0';
        for (int i = length - 1; i >= 0; i--) {
            if (arr[i] + v >= max) {
                arr[i] = (char) (arr[i] + v - k);
                v = 1;
            } else {
                arr[i] = (char) (arr[i] + v);
                return arr;
            }
        }
        return null;
    }

    private long getValue(char[] arr, int k) {
        int length = arr.length;
        long v = 0;
        long t = 1;
        for (int i = length - 1; i >= 0; i--) {
            v = v + t * (arr[i] - '0');
            t = t * k;
        }
        return v;
    }

}
